package com.tgy.algorithm.base._二叉树;

import javax.swing.tree.TreeNode;
import java.util.Stack;

class BiTreeNode {
    int val;
    BiTreeNode left;
    BiTreeNode right;
    BiTreeNode(int x) {
        val = x;
    }
}


public class _二叉树的遍历 {

    public static BiTreeNode getBiTreeNode() {

        /**
         *          1
         *      2         3
         *   4    5     6     7
         */
        BiTreeNode header = new BiTreeNode(1);
        header.left = new BiTreeNode(2);
        header.right = new BiTreeNode(3);
        header.left.left = new BiTreeNode(4);
        header.left.right = new BiTreeNode(5);
        header.right.left = new BiTreeNode(6);
        header.right.right = new BiTreeNode(7);
        return header;
    }

    public static void biTreeRecursiveOrder(BiTreeNode root) {

        if (root == null) {
            return;
        }

//        System.out.println(root.val);
        biTreeRecursiveOrder(root.left);
        System.out.println(root.val);
        biTreeRecursiveOrder(root.right);
//        System.out.println(root.val);
    }

    // 二叉树先序遍历
    public static void biTreePreOrder(BiTreeNode root) {

        if (root == null) {
            return;
        }

        Stack<BiTreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            BiTreeNode node = stack.pop();
            System.out.println(node.val);
            // 先进后出
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
    
    // 二叉树后序遍历第一种实现，利用前序的顺序
    public static void biTreePostOrder01(BiTreeNode root) {
        if (root == null) {
            return;
        }
        Stack<BiTreeNode> stack = new Stack<>();
        stack.push(root);
        Stack<BiTreeNode> backStack = new Stack<>();
        while (!stack.isEmpty()) {
            BiTreeNode pop = stack.pop();
            backStack.push(pop);
            if (pop.left != null) {
                stack.push(pop.left);
            }

            if (pop.right != null) {
                stack.push(pop.right);
            }
        }

        while (!backStack.isEmpty()) {
            System.out.println(backStack.pop().val);
        }
    }


    public static void biTreeInorder(BiTreeNode root) {

        if (root == null) {
            return;
        }

        /**
         *          1
         *      2         3
         *   4    5     6     7
         */

        Stack<BiTreeNode> stack = new Stack<>();
        BiTreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }else {
                BiTreeNode pop = stack.pop();
                System.out.println(pop.val);
                cur = pop.right;
            }
        }

    }

    public static void main(String[] args) {
        BiTreeNode biTreeNode = getBiTreeNode();
//        biTreeRecursiveOrder(biTreeNode);
//        biTreePreOrder(biTreeNode);
        biTreePostOrder01(biTreeNode);
    }
}
